package com.chapter5.string;

/**
 * 
 * @ClassName: MSD
 * @Description: 高位优先排序
 * 
 *               思想跟快速排序一样，采用分治方法。
 *               首先利用键索引计数法，对字符串数组的左起第一个元素排序，排好后，将第二个元素相同部分分别递归的利用建索引计数法排序
 *               直到所有元素排列完成
 *               
 *               原生的高位优先排序会产生大量的子数组，也就会产生大量int[] count=new int[R+2]对象,对象长度256+2，这样会浪费大量时间和空间，需要改进。
 *               可以考虑在大数组切分成小数组之后，利用插入排序处理（稳定）
 *               
 *               虽然做了如上优化，但是高位优先排序的空间碰到大量重复的字符串，将会检查几乎所有碰到的字符，时间会是线性级别的。并且很重要的一点，MSD会制造大量的小数组，浪费空间。
 *               而与MSD相似的快速排序则可以节省很多空间，但是快速排序处理字符串的时候，时间复杂度为Nlg2N。无法满足速度上的要求。
 *               可以结合MSD和快速排序的优点来实现一种新的排序方法--三向字符串排序
 * 
 * @author minjun
 * @date 2015年3月17日 下午8:54:35
 * 
 */
public class MSD {

	private static final int R = 65536;

	private static String[] aux;

	private static final int M=15;

	public static void sort(String[] s) {
		aux = new String[s.length];
		sort(s, 0, s.length - 1, 0);
	}

	private static void sort(String[] s, int start, int end, int pos) {
		if (end<=start+M){
			insertionSort(s, start, end, pos);
			return;
		}
//		if (end<=start){
//			return;
//		}
		// 找到相同部分，切分开
		// 需要一个多余的空位用来存储-1
		int[] count = new int[R + 2];

		// 计数
		// 由于需要将-1存入count[]，并将-1置为最小元素，并且索引不能为负数，所以可以将所有索引暂时+1(由于key_index算法，这里继续+1)，这样-1索引编程0，以此类推。。。
		for (int i = start; i <= end; i++) {
			count[charAt(s[i], pos) + 2]++;
		}

		// 索引
		for (int i = 0; i < R + 1; i++) {
			count[i + 1] += count[i];
		}

		// 插入
		// 需要将计算出来的索引位置+1才能正确的拿到count中对应的值
		for (int i = start; i <= end; i++) {
			aux[start + count[charAt(s[i], pos) + 1]++] = s[i];
		}

		// 复制
		for (int i = start; i <= end; i++) {
			s[i] = aux[i];
		}

		// 分治处理
		for (int i = 0; i < R; i++) {
			sort(s, start + count[i], start + count[i + 1] - 1, pos + 1);
		}
	}

	/**
	 * 
	 * @Title: toChar
	 * @Description: 获取指定位置的元素，如果超出了字符串，那么就用-1表示这个元素（表示该元素比任何一个字符元素都要小）
	 * @param @param s
	 * @param @param pos
	 * @param @return 设定文件
	 * @return int 返回类型
	 * @throws
	 */
	private static int charAt(String s, int pos) {
		return pos < s.length() ? s.charAt(pos) : -1;
	}

	private static void insertionSort(String[] a,int start,int end, int pos) {
		for (int i = start+1; i <=end; i++) {
			for (int j = i; j > start && less(a[j], a[j - 1], pos); j--) {
				swap(a, j - 1, j);
			}
		}
		System.out.println("insertion sort");
	}

	private static void swap(String[] a, int i, int j) {
		String temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	private static boolean less(String a, String b, int pos) {
		return a.substring(pos).compareTo(b.substring(pos)) < 0;
	}

}
